# -*- coding: utf-8 -*-
# @Time : 2024/2/20 10:01
# @Author : ZH
# @File : 106.py
# @Software: PyCharm
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int] # 中序
        :type postorder: List[int]  # 后序
        :rtype: TreeNode
        """
        # 后序遍历的最后一个元素是根元素的节点
        if not postorder:
            return None
        root_val = postorder[-1]
        root = TreeNode(root_val)
        if len(postorder) == 1:
            return root

        # 寻找中序遍历中元素的位置
        val_index = inorder.index(root_val)
        root.left = self.buildTree(inorder=inorder[:val_index], postorder=postorder[:val_index])
        root.right = self.buildTree(inorder=inorder[val_index+1:], postorder=postorder[val_index:-1])
        return root

if __name__ == '__main__':
    # inorder = [9, 3, 15, 20, 7]
    # postorder = [9,15,7,20,3]
    inorder = [2, 1]
    postorder = [2, 1]
    so = Solution()
    z = so.buildTree(inorder=inorder, postorder=postorder)
    print()

